//https://leetcode.cn/problems/trapping-rain-water/submissions/499457651/?envType=study-plan-v2&envId=top-100-liked
//方法1:动态规划：1.对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值2.下标i处能接的雨水量等于下标i处的水能到达的最大高度减去 height[i]；
//方法2:使用双指针解决；
//方法3:单调栈解决；

#include <iostream>
#include <vector>
#include <map>
#include<unordered_map>
#include <algorithm>
#include <stack>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        std::stack<std::list<int>> stack;
        int ans=0;
        for(size_t i=0;i<height.size();++i){
            while(!stack.empty()&& height[stack.top().back()] < height[i]) {
                std::list<int> popIs=stack.top();
                stack.pop();
                if(stack.empty()){
                    break;
                }
                int currHeight = std::min(height[stack.top().back()],height[i]) - height[popIs.back()];
                int currWidth = i - stack.top().back() - 1;
                ans+=currHeight*currWidth;
            }
            if(!stack.empty() && height[stack.top().back()] == height[i]) {
                stack.top().push_back(i);
            }else{
                std::list<int> list = {(int)i};
                stack.push(list);
            }
        }
        return ans;
    } 
};